class BTree:
    def __init__(self,x):
        self.val =x
        self.right = None
        self.left = None
    def preorder(self):
        if self.val is not None:
            print(self.val)
        if self.left is not None:
            self.left.preorder()
        if self.right is not None:
            self.right.preorder()
    def inorder(self):
        if self.left is not None:
            self.left.inorder()
        if self.val is not None:
            print(self.val, end=' ')
        if self.right is not None:
            self.right.inorder()

def recursive_preorder(root):
    stack = [root]
    while stack:
        s = stack.pop()
        if s:
            print(s.val)
            stack.append(s.right)
            stack.append(s.left)
def inorder(root):
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        print(root.val)
        root = root.right


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root):
        ans = list()

        stack = list()

        while stack or root:
            while root:
                # 前序遍历，先添加一个
                ans.append(root.val)
                # 将左边的节点压入栈中
                stack.append(root)
                root = root.left
            # 从栈中弹出最后一个node
            root = stack.pop()
            # 去看这个node的右节点
            root = root.right

        return ans


if __name__=="__main__":
    right_tree = BTree("C")
    right_tree.right = BTree("F")

    left_tree = BTree("B")
    left_tree.right=BTree("E")
    left_tree.left=BTree("D")

    tree = BTree("A")
    tree.left = left_tree
    tree.right = right_tree
    print(recursive_preorder(tree))
    # right_tree = BTree(6)
    # right_tree.left = BTree(2)
    # right_tree.right = BTree(4)
    #
    # left_tree = BTree(5)
    # left_tree.left = BTree(1)
    # left_tree.right = BTree(3)
    #
    # tree = BTree(11)
    # tree.left = left_tree
    # tree.right = right_tree
    #
    # left_tree = BTree(7)
    # left_tree.left = BTree(3)
    # left_tree.right = BTree(4)
    #
    # right_tree = tree # 增加新的变量
    # tree = BTree(18)
    # tree.left = left_tree
    # tree.right = right_tree


